#include<stdio.h>
#include<stdlib.h>

#define infinity 32756
int n,m;
int *d;
int **mt;

int *q;
int tail;
int deq(){
    int i=q[0];
    for(int j=1;j<=tail;j++){
        q[j-1]=q[j];
    }
    tail--;
    return i;
}
void enq(int item){
    q[tail++]=item;
}

int main(){
    //freopen("poj_1014.txt","r",stdin);

    int i,j;
    scanf("%d %d",&n,&m);

    q=(int*)malloc(2*n*sizeof(int));
    tail=0;

    d=(int*)malloc((n+1)*sizeof(int));
    mt=(int**)malloc((n+1)*sizeof(int*));
  
    for(i=0;i<n+1;i++){
        mt[i]=(int*)malloc((n+1) * sizeof(int*));
        for(j=0;j<n+1;j++){
            mt[i][j]=-1;            
        }
        d[i]=infinity;
    }
    d[1]=0;

    int u,v,w;
    for(i=0;i<m;i++){
        scanf("%d %d %d",&u,&v,&w);
        mt[u][v]=w;
    }

    enq(1);

    while(tail>0){
        v=deq();

        for(j=1 ; j<n+1 ; j++){
            if(j!=v && mt[v][j]!=-1){
                enq(j);
                if(d[v] + mt[v][j] < d[j]){
                    d[j] = d[v] + mt[v][j];
                }
            }
        }
    }

    printf("%d\n",d[n]);

    return 0;
}